public class IsMatch {

    public static void main(String[] args) {
        IsMatch isMatch = new IsMatch();
        System.out.println(isMatch.isMatch("aab", "c*a*b"));
    }

    boolean[][] dp;
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        char[] sChars = s.toCharArray();
        char[] pChars = p.toCharArray();
        dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 0; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                dp[i][j] = check(pChars, sChars, i, j);
            }
        }
        return dp[m][n];
    }

    public boolean check(char[] pChars, char[] sChars, int i, int j) {
        if (i == 0) {
            return pChars[j - 1] == '*' && dp[i][j - 2];
        }
        char c1 = sChars[i - 1];
        char c2 = pChars[j - 1];
        if (Character.isLetter(c2) || c2 == '.') {
            return (c1 == c2 || c2 == '.') && dp[i - 1][j - 1];
        } else {
            char c3 = pChars[j - 2];
            return c3 == c1 || c3 == '.' ? dp[i - 1][j] || dp[i][j - 2] : dp[i][j - 2];
        }
    }
}
